This invention relates to hierarchical data storage systems.
A hierarchical data storage system basically comprises a first, relatively large store, in conjunction with a second store which is smaller but faster than the first store. The second store is arranged to hold copies of data items which have recently been used and therefore have a high probability of being required again in the near future. As a result, a high proportion of data retrieval requests can be satisfied simply by reading the data from the second store, without the need for access to the first store. In this way, the system can achieve a fast average data access speed, ideally approaching that of the second store, but with a low average cost per bit of storage, approaching that of the first store.
In such a system, when it is desired to modify a particular data item, a check is first made to find out whether that item is currently resident in the second store and, if so, a write operation is performed in the second store so as to make the required modification. It is then necessary at some time to perform a corresponding write operation in the first store, so as to ensure that the first store is kept up-to-date. Various strategies for performing the writing of data to the first store have been proposed, as follows:
(a) Whenever a data item is written into the second store, it is also immediately written into the first store. This is the simplest strategy, but has the disadvantage that it results in the maximum number of accesses to the first store. Moreover, modification of a data item is a slow process, since it always involves access to the first store. PA1 (b) When a data item is written into the second store, it is not immediately written into the first store; it is written to the first store only when the item is about to be deleted from the second store. The advantage of this strategy is that the number of accesses to the first store is minimised since, if a data item is modified several times while it is resident in the second store, only the last of the modified values is actually written into the first store. The disadvantage, however, is that deletion of a data item is a slow process, since it involves access to the first store. This is particularly evident when it is desired to clear the second store completely, which may involve a large number of accesses to the first store and hence take a relatively long time. PA1 (c) British Patent Specification No. 1233117, as well as describing strategies (a) and (b) above, also describes another strategy in which, when a data item is written into the second store, a "changed" bit is set for that item, but the item is not immediately written into the first store. Instead, when the first store has free time available, a low priority request is made for access to the second store. When this request is granted, the second store is searched for items whose changed bits have been set, and these items are transferred to the first store. Searching continues until all the second store has been searched, or until it is interrupted by a higher priority request for use of the second store. This method removes some of the disadvantages of (a) and (b) above, but requires additional hardware for resolving different priority requests. Moreover, the searching of the second store could introduce a further delay.
The object of the present invention is to alleviate the problems of (a) and (b) above, without the necessity for priority resolution hardware and without the need for searching the second store for changed items.